package learn;

public class ErfengChaZhao {
    public static void main(String[] args) {

        int[] arr = {1, 2, 3, 4, 5, 6, 7,  8, 10, 11, 12,13, 14, 16, 17, 18, 19};
 //       int leftest = ErfengChaZhao.exist(arr, 20);
//        System.out.println("index : " + leftest);
//        int leftest = ErfengChaZhao.leftest(arr, 15);
//        System.out.println("leftest : " + leftest);

        System.out.println(rightest(arr, 9));
        System.out.println(leftest(arr, 9));
    }

    /**
     * 用二分查找法完成
     * 找到index，arr[index]==val 且是数组最左边的index
     *
     * @param arr 给定的数组
     * @param val 给定的值
     * @return
     */
    public static int exist(int[] arr, int val) {
        int l = 0;
        int r = arr.length - 1;
        while (l < r) {
            int mid = ((r - l) >>> 1) + l;
            if (val == arr[mid]) {
                return mid;
            } else if (val > arr[mid]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return -1;
    }
    /**
     * 用二分查找法完成
     * 找到index，arr[index]>=var 且是数组最左边的index
     *
     * @param arr 给定的数组
     * @param val 给定的值
     * @return
     */
    public static int leftest(int[] arr, int val) {
        int l = 0;
        int r = arr.length - 1;
        int index =-1;
        while (l <= r) {
            int mid = ((r - l) >> 1) + l;
            if (val <= arr[mid]) {
                index = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return index;
    }

    /**
     * 用二分查找法完成
     * 找到index，arr[index]<=val 且是数组最右边的index
     *
     * @param arr 给定的数组
     * @param val 给定的值
     * @return
     */
    public static int rightest(int[] arr, int val) {
        int l = 0;
        int r = arr.length - 1;
        int index =-1;
        while (l <= r) {
            int mid = ((r - l) >> 1) + l;
            if (val >= arr[mid]) {
                index = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return index;
    }



}

